package algorithm.t202110;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/31 8:59
 * @description :6道
 * 世界之大。
 * persevere to last
 * 2021.10.31
 * 李红磊
 * 十月，匆匆滑过。
 */
public class t20211031 {
    //500.键盘行
    static public String[] findWords(String[] words) {
        if (words == null || words.length == 0) {
            return new String[]{};
        }
        String one = "qwertyuiop";
        String two = "asdfghjkl";
        String three = "zxcvbnm";

        ArrayList<String> res = new ArrayList<>();

        for (String element : words) {
            String lowCase = element.toLowerCase();


            char firstWord = lowCase.charAt(0);

            if (one.indexOf(firstWord) != -1) {
                boolean flag = true;
                for (int i = 1; i < element.length(); i++) {
                    if (one.indexOf(lowCase.charAt(i)) == -1) {
                        flag = false;
                        break;
                    }

                }
                if (flag) {
                    res.add(element);
                }
            } else if (two.indexOf(firstWord) != -1) {
                boolean flag = true;
                for (int i = 1; i < element.length(); i++) {
                    if (two.indexOf(lowCase.charAt(i)) == -1) {
                        flag = false;
                        break;
                    }

                }
                if (flag) {
                    res.add(element);
                }
            } else if (three.indexOf(firstWord) != -1) {
                boolean flag = true;
                for (int i = 1; i < element.length(); i++) {
                    if (three.indexOf(lowCase.charAt(i)) == -1) {
                        flag = false;
                        break;
                    }

                }
                if (flag) {
                    res.add(element);
                }
            }


        }

        return res.toArray(new String[0]);
    }

    //1091.二进制矩阵中的最短路径
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null) {
            return -1;
        }
        int rows = grid.length, columns = grid[0].length;
        if (grid[0][0] == 1 || grid[rows - 1][columns - 1] == 1) {
            return -1;
        }
        int res = 0;


        boolean[][] visit = new boolean[rows][columns];//备忘录，记录已经访问过的位置

        LinkedList<int[]> queue = new LinkedList<>();

        queue.offer(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();//取出队列头位置

                int x = cur[0];
                int y = cur[1];
                if (x == rows - 1 && y == columns - 1) {//查看是否已经走到了终点
                    return res + 1;
                }

                //枚举出下一步的所有可能【共八个，八个方向
                int[][] temp = {
                        {x - 1, y},
                        {x + 1, y},
                        {x, y - 1},
                        {x, y + 1},
                        {x - 1, y - 1},//左上
                        {x + 1, y - 1},//左下
                        {x - 1, y + 1},//右上
                        {x + 1, y + 1}//右下
                };

                //对可能的方向进行过滤
                for (int[] arr : temp) {

                    //边界条件
                    if (arr[0] < 0 || arr[0] > rows - 1 | arr[1] < 0 || arr[1] > columns - 1 ||
                            grid[arr[0]][arr[1]] == 1) {
                        continue;
                    }

                    //备忘录检查
                    if (visit[arr[0]][arr[1]]) {
                        continue;
                    }

                    //经过过滤之后，加入队列，并在备忘录中记录
                    visit[arr[0]][arr[1]] = true;
                    queue.offer(arr);
                }

            }
            res++;

        }


        return grid[rows - 1][columns - 1] == 1 ? res : -1;
    }


    //130.被围绕的区域
    public void solve(char[][] board) {
        if (board == null) {
            return;
        }

        int rows = board.length, columns = board[0].length;
        //备忘录
        boolean[][] visit = new boolean[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == 'O') {
                    if (dfs(board, i, j, rows, columns, visit)) board[i][j] = 'X';
                }

            }
        }

    }

    private boolean dfs(char[][] board, int x, int y, int rows, int columns, boolean[][] visit) {
        if (x < 0 || x > rows - 1 || y < 0 || y > columns - 1) {
            return false;
        }
        if (board[x][y] == 'X' || visit[x][y]) {
            return true;
        }
        visit[x][y] = true;

        boolean flag = dfs(board, x - 1, y, rows, columns, visit) && dfs(board, x + 1, y, rows, columns, visit)
                && dfs(board, x, y - 1, rows, columns, visit) && dfs(board, x, y + 1, rows, columns, visit);

        visit[x][y] = false;

        return flag;
    }

    public void solve2(char[][] board) {
        if (board == null) {
            return;
        }

        int rows = board.length, columns = board[0].length;

        //先对和边界联通的的'O'做处理
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                //判断现在是否处于边界
                boolean isEdge = i == 0 || i == rows - 1 || j == 0 || j == columns - 1;

                if (isEdge && board[i][j] == 'O') {//找到了与边界联通的‘O’
                    //现在对所有与此’O'连接的'O'做处理（因为只要和这个'O'连接了，说明你也是和边界想通的
                    dfs2(board, i, j);
                }

            }
        }

        //再对所有和边界相通的’O‘做完处理之后，现在矩阵中剩下的’O‘都被X所包围
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                //将边界O【#】还是复位成O
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }


    }

    private void dfs2(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 'X' || board[x][y] == '#') {
            return;
        }
        board[x][y] = '#';
        //再对上下左右四个方向 看看还有没有与此边界O相通的
        dfs2(board, x - 1, y);
        dfs2(board, x + 1, y);
        dfs2(board, x, y - 1);
        dfs2(board, x, y + 1);

    }


    //797.所有可能的路径
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (graph == null || graph.length == 0) {
            return res;
        }

        ArrayList<Integer> cur = new ArrayList<>();
        int count = graph.length;//表示节点的个数
        cur.add(0);//将第一个节点加入


        dfs3(0, graph, count, cur, res);
        return res;

    }

    /**
     * @Author 李红磊
     * @Date 2021/10/31 15:03
     * @param: node 当前节点
     * @param: graph  有向无环图
     * @param: count 总节点数量
     * @param: cur 当前路径
     * @param: res 用于返回
     **/
    private void dfs3(int node, int[][] graph, int count, ArrayList<Integer> cur, ArrayList<List<Integer>> res) {
        if (node == count - 1) {
            //表面已经是最后一个节点了
            res.add(new ArrayList<>(cur));
            return;
        }
        for (int item : graph[node]) {
            cur.add(item);
            dfs3(item, graph, count, cur, res);
            cur.remove(cur.size() - 1);
        }

    }

    //面试题08.09 括号
    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        dfs4("", n, n, res);
        return res;

    }

    /**
     * @Author 李红磊
     * @Date 2021/10/31 16:01
     * @param: cur 当前拼接的字符串
     * @param: leftNum 左括号的剩余数量
     * @param: rightNum 右括号的剩余数量
     * @param: res 用于返回的集合
     **/
    private void dfs4(String cur, int leftNum, int rightNum, ArrayList<String> res) {
        if (leftNum == 0 && rightNum == 0) {
            res.add(cur);
            return;
        }

        //剪枝
        if (leftNum > rightNum) {
            return;
        }

        if (leftNum > 0) {
            dfs4(cur + "(", leftNum - 1, rightNum, res);
        }
        if (rightNum > 0) {
            dfs4(cur + ")", leftNum, rightNum - 1, res);
        }

    }


    //面试题08.11 硬币
    public int waysToChange(int n) {
        int[] coins = {1, 5, 10, 25};
        int[][] dp = new int[coins.length][n + 1];

        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        //现在开始判断
        /*
            dp[i][j]:j表示背包容量，i表示物品编号，ci表示i编号物品对应的体积
         */
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (coins[i] > n) {
                    //拿不下，物品太大
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //拿到
                    dp[i][j] = (dp[i - 1][j] + dp[i][n - coins[i]]) % 1000000007;
                }
            }
        }

        return dp[coins.length - 1][n];
    }

    public int waysToChange2(int n) {
        int[] coins = {1, 5, 10, 25};
        int[][] dp = new int[4][n + 1];

        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < 4; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i < 4; i++) {
            for (int j = 1; j <= n; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - coins[i]]) % 1000000007;
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[3][n];

    }

    public int waysToChange3(int n) {

        int[] coins = {1, 5, 10, 25};

        int[][] dp = new int[4][n + 1];

        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
        }

        for (int i = 0; i < 4; i++) {
            dp[i][0] = 1;
        }


        for (int i = 1; i < 4; i++) {
            for (int j = 1; j <= n; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = (dp[i - 1][j] + dp[i][n - coins[i]]) % 1000000007;
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[3][n];

    }

    //面试题08.12 八皇后
    public List<List<String>> solveNQueens(int n) {
        ArrayList<List<String>> res = new ArrayList<>();
        if (n == 0) return res;


        char[][] chess = new char[n][n];
        //初始化数组
        for (int i = 0; i < chess.length; i++) {
            for (int j = 0; j < chess[0].length; j++) {
                chess[i][j] = '.';
            }
        }

        solveQ(chess, 0, res);


        return res;
    }

    private void solveQ(char[][] chess, int row, ArrayList<List<String>> res) {
        if (row == chess.length) {
            //表面已经放到最后一行

        }

        for (int col = 0; col < chess.length; col++) {
            if (isValid(row, col, chess)) {

            }

        }


    }

    private boolean isValid(int row, int col, char[][] chess) {
        //判断在当前【行，列】放置皇后是否合理

        //先检查当前列上有没有皇后
        for (int i = 0; i < row; i++) {
            if (chess[i][col] == 'Q') {
                return false;
            }
        }

        //判断当前坐标的右上角有没有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length - 1; i--, j++) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }

        //判断当前坐标的左上角有没有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }


    public static void main(String[] args) {
        t20211031 t20211031 = new t20211031();

        char[][] chars = {
                {'O', 'O', 'O'},
                {'O', 'O', 'O'},
                {'O', 'O', 'O'}
        };


        System.out.println(t20211031.waysToChange2(10));


    }

}
